package recursion_DynamicProgramming;

//给定一个整型数组arr，代表数值不同的纸牌排成一条线
//        玩家A和玩家B依次拿走每张纸牌
//        规定玩家A先拿，玩家B后拿
//        但是每个玩家每次只能拿走最左或最右的纸牌
//        玩家A和玩家B都绝顶聪明
//        请返回最后获胜者的分数。
public class Task02 {
    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
//        System.out.println(win1(arr));
        System.out.println(win2(arr));

    }
    public static int win2(int[] arr) {
        //限定的条件
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];

        for (int i = 0; i <N; i++) {
            for (int j = 0; j <N; j++) {
                fmap[i][j]=-1;
                gmap[i][j]=-1;
            }
        }
        System.out.println(fmap);
        System.out.println(gmap);
        int first = f2(arr, 0, arr.length - 1, fmap, gmap);
        int next = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, next);

    }
    //Arr[L..R] 先手获得最好的分数返回
    public static int f2(int[] arr, int L, int R, int[][] famp, int[][] gmap) {
        if (famp[L][R]!= -1) {
            return famp[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        }
        int p1 = arr[L] + g2(arr, L + 1, R, famp, gmap);
        int p2 = arr[R] + g2(arr, L, R - 1, famp, gmap);
        ans = Math.max(p1, p2);
        famp[L][R] = ans;
        return ans;
    }

    public static int g2(int[] arr, int L, int R, int[][] famp, int[][] gmap) {
        if (gmap[L][R]!= -1) {
            return gmap[L][R];
        }
        int ans = 0;
        if (L != R) {
            //最大的这个被先手拿掉了
            int p1 = f2(arr, L + 1, R, famp, gmap);
            int p2 = f2(arr, L, R - 1, famp, gmap);
            ans = Math.min(p1, p2);
            gmap[L][R] = ans;
        }
        return ans;
    }


    //根据规则返回获胜者方法
    public static int win1(int[] arr) {
        //限定的条件
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int first = f(arr, 0, arr.length - 1);
        int next = g(arr, 0, arr.length - 1);
        return Math.max(first, next);

    }
    //Arr[L..R] 先手获得最好的分数返回
    public static int f(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int p1 = arr[L] + g(arr, L + 1, R);
        int p2 = arr[R] + g(arr, L, R - 1);
        return Math.max(p1, p2);


    }

    public static int g(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        //最大的这个被先手拿掉了
        int p1 = f(arr, L + 1, R);
        int p2 = f(arr, L, R - 1);
        return Math.min(p1, p2);
    }
}
